{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Add Edges to Make Degrees of All Nodes Even"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPossible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #添加边使所有节点度数都为偶数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个有 <code>n</code>&nbsp;个节点的 <strong>无向</strong>&nbsp;图，节点编号为&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;。再给你整数&nbsp;<code>n</code>&nbsp;和一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条边。图不一定连通。</p>\n",
    "\n",
    "<p>你可以给图中添加 <strong>至多</strong>&nbsp;两条额外的边（也可以一条边都不添加），使得图中没有重边也没有自环。</p>\n",
    "\n",
    "<p>如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回&nbsp;<code>true</code>&nbsp;，否则返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>点的度数是连接一个点的边的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/26/agraphdrawio.png\" style=\"width: 500px; height: 190px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>上图展示了添加一条边的合法方案。\n",
    "最终图中每个节点都连接偶数条边。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/26/aagraphdrawio.png\" style=\"width: 400px; height: 120px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, edges = [[1,2],[3,4]]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>上图展示了添加两条边的合法方案。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/26/aaagraphdrawio.png\" style=\"width: 150px; height: 158px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, edges = [[1,2],[1,3],[1,4]]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>无法添加至多 2 条边得到一个符合要求的图。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= edges.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>图中不会有重边</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [add-edges-to-make-degrees-of-all-nodes-even](https://leetcode.cn/problems/add-edges-to-make-degrees-of-all-nodes-even/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [add-edges-to-make-degrees-of-all-nodes-even](https://leetcode.cn/problems/add-edges-to-make-degrees-of-all-nodes-even/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]', '4\\n[[1,2],[3,4]]', '4\\n[[1,2],[1,3],[1,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        degrees = [0]*(n+1)\n",
    "        for a, b in edges:\n",
    "            degrees[a] += 1\n",
    "            degrees[b] += 1\n",
    "        singles = set()\n",
    "        for i, v in enumerate(degrees[1:], 1):\n",
    "            if v & 1:\n",
    "                singles.add(i)\n",
    "        NS = len(singles)\n",
    "        if not NS: return True\n",
    "        if NS > 4 or NS & 1: return False\n",
    "        if NS == 2:\n",
    "            nexts = defaultdict(set)\n",
    "            for a, b in edges:\n",
    "                if a in singles:\n",
    "                    nexts[a].add(b)\n",
    "                if b in singles:\n",
    "                    nexts[b].add(a)\n",
    "            return not (singles & next(iter(nexts.values()))) or n > len(reduce(or_, (nexts[v] for v in singles), singles))\n",
    "        c = Counter()\n",
    "        for a, b in edges:\n",
    "            if a in singles and b in singles:\n",
    "                c[a] += 1\n",
    "                c[b] += 1\n",
    "        cc = Counter(c.values())        \n",
    "        return cc[3] == 0 and cc[2] != 3\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        h = [[] for _ in range(n+1)]\n",
    "        for a, b in edges:\n",
    "            h[a].append(b)\n",
    "            h[b].append(a)\n",
    "\n",
    "        ji_nodes = []\n",
    "        for i in range(1, n+1):\n",
    "            if len(h[i]) % 2 == 1:\n",
    "                ji_nodes.append(i)\n",
    "\n",
    "        if not ji_nodes:\n",
    "            return True\n",
    "\n",
    "        def find_not_tong(node):\n",
    "            res = []\n",
    "            for i in range(1, n+1):\n",
    "                if i == node:\n",
    "                    continue\n",
    "                if node not in h[i]:\n",
    "                    res.append(i)\n",
    "            return res\n",
    "\n",
    "        def helper(a, b):\n",
    "            if b in h[a]:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        l = len(ji_nodes)\n",
    "        if l > 4 or l in [1,3]:\n",
    "            return False\n",
    "        if l == 2:\n",
    "            a, b = ji_nodes\n",
    "            if helper(a, b):\n",
    "                return True\n",
    "            not_a_list = find_not_tong(a)\n",
    "            not_b_list = find_not_tong(b)\n",
    "            #print(not_a_list)\n",
    "            #print(not_b_list)\n",
    "            for not_a in not_a_list:\n",
    "                for not_b in not_b_list:\n",
    "                    if not_a == not_b:\n",
    "                        return True\n",
    "                    if not helper(not_a, not_b):\n",
    "                        return True\n",
    "            return False\n",
    "            \n",
    "        if l == 4:\n",
    "            a, b, c, d = ji_nodes\n",
    "            if (helper(a,b) and helper(c, d)) or (helper(a,c) and helper(b, d)) or (helper(a,d) and helper(b, c)):\n",
    "                return True\n",
    "            return False \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        cand = [i for i,x in g.items() if len(x) & 1]    \n",
    "        l = len(cand)\n",
    "        if l == 0: return True\n",
    "        if l == 2:\n",
    "            a, b = cand\n",
    "            if a not in g[b]: return True\n",
    "            for i in range(1,n+1):\n",
    "                if a not in g[i] and b not in g[i] and a in g[b]:\n",
    "                    return True\n",
    "            return False\n",
    "        if l == 4:\n",
    "            a, b, c, d = cand\n",
    "            if a not in g[b] and c not in g[d]: return True\n",
    "            if a not in g[c] and b not in g[d]: return True\n",
    "            if a not in g[d] and b not in g[c]: return True\n",
    "        return False\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        # 建图\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            u, v = u - 1, v - 1\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        q = [x for x, np in enumerate(g) if len(np) % 2]\n",
    "\n",
    "        m = len(q)\n",
    "\n",
    "        if m == 2:\n",
    "            x, y = q\n",
    "            if x not in g[y]:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if i != x and i != y and x not in g[i] and y not in g[i]:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        if m == 4:\n",
    "            a, b, c, d = q\n",
    "            return  a not in g[b] and c not in g[d] or a not in g[c] and b not in g[d] or a not in g[d] and b not in g[c]\n",
    "\n",
    "        return m == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            neighbors[i - 1].append(j - 1)\n",
    "            neighbors[j - 1].append(i - 1)\n",
    "        odd = []\n",
    "        for i in range(n):\n",
    "            if len(neighbors[i]) % 2 == 1: odd.append(i)\n",
    "        print(odd)\n",
    "        if len(odd) > 4 or len(odd) % 2 == 1: return False\n",
    "        if len(odd) == 0: return True\n",
    "        def iso(i, j):\n",
    "            return i != j and (j not in neighbors[i])\n",
    "        if len(odd) == 2:\n",
    "            for i in range(n):\n",
    "                if iso(i, odd[0]) and iso(i, odd[1]):\n",
    "                    return True\n",
    "            if iso(odd[0], odd[1]):\n",
    "                return True\n",
    "            return False\n",
    "        else:\n",
    "            if iso(odd[0], odd[1]) and iso(odd[2], odd[3]): \n",
    "                return True\n",
    "            if iso(odd[0], odd[2]) and iso(odd[1], odd[3]): \n",
    "                return True\n",
    "            if iso(odd[0], odd[3]) and iso(odd[1], odd[2]): \n",
    "                return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = [0 for _ in range(n)]\n",
    "        odd,even = [],[]\n",
    "        s = set()\n",
    "        for u,v in edges:\n",
    "            g[u-1]+=1\n",
    "            g[v-1]+=1\n",
    "            s.add((u,v))\n",
    "        for i in range(n):\n",
    "            if g[i]%2==1:\n",
    "                odd.append(i+1)\n",
    "            else:\n",
    "                even.append(i+1)\n",
    "        if not odd:\n",
    "            return True\n",
    "        elif len(odd)==2:\n",
    "            if ((odd[0],odd[1]) not in s) and ((odd[1],odd[0]) not in s):\n",
    "                return True\n",
    "            else:\n",
    "                for node in range(1,n+1):\n",
    "                    if node==odd[0] or node==odd[1]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        if (((node,odd[0]) not in s) and ((odd[0],node) not in s)) and (((node,odd[1]) not in s) and ((odd[1],node) not in s)):\n",
    "                            return True\n",
    "                return False\n",
    "        elif len(odd)==4:\n",
    "            dic = [0,0,0,0]\n",
    "            for i in range(4):\n",
    "                for j in range(i+1,4):\n",
    "                    if (odd[i],odd[j]) in s or (odd[j],odd[i]) in s:\n",
    "                        dic[i]+=1\n",
    "                        dic[j]+=1\n",
    "                        if dic[i]>=3 or dic[j]>=3:\n",
    "                            return False\n",
    "            if sorted(dic)==[0,2,2,2]:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = [0 for _ in range(n)]\n",
    "        odd,even = [],[]\n",
    "        s = set()\n",
    "        for u,v in edges:\n",
    "            g[u-1]+=1\n",
    "            g[v-1]+=1\n",
    "            s.add((u,v))\n",
    "        for i in range(n):\n",
    "            if g[i]%2==1:\n",
    "                odd.append(i+1)\n",
    "            else:\n",
    "                even.append(i+1)\n",
    "        if not odd:\n",
    "            return True\n",
    "        elif len(odd)==2:\n",
    "            if ((odd[0],odd[1]) not in s) and ((odd[1],odd[0]) not in s):\n",
    "                return True\n",
    "            else:\n",
    "                for node in range(1,n+1):\n",
    "                    if node==odd[0] or node==odd[1]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        if (((node,odd[0]) not in s) and ((odd[0],node) not in s)) and (((node,odd[1]) not in s) and ((odd[1],node) not in s)):\n",
    "                            return True\n",
    "                return False\n",
    "        elif len(odd)==4:\n",
    "            dic = [0,0,0,0]\n",
    "            for i in range(4):\n",
    "                for j in range(i+1,4):\n",
    "                    if (odd[i],odd[j]) in s or (odd[j],odd[i]) in s:\n",
    "                        dic[i]+=1\n",
    "                        dic[j]+=1\n",
    "                        if dic[i]>=3 or dic[j]>=3:\n",
    "                            return False\n",
    "            if sorted(dic)==[0,2,2,2]:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        new = [node for node in range(1, n + 1) if len(graph[node]) % 2]\n",
    "        if not new:\n",
    "            return True \n",
    "        if len(new) == 2:\n",
    "            a, b = new \n",
    "            if b not in graph[a] and a not in graph[b] or any(node not in graph[a] and node not in graph[b] for node in range(1, n + 1)):\n",
    "                return True \n",
    "        elif len(new) == 4:\n",
    "            a, b, c, d = new \n",
    "            if b not in graph[a] and d not in graph[c] or c not in graph[a] and b not in graph[d] or d not in graph[a] and b not in graph[c]:\n",
    "                return True \n",
    "        return False \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i,nb in g.items() if len(nb) %2]\n",
    "        m = len(odd)\n",
    "        if m==0: return True\n",
    "\n",
    "        if m==2:\n",
    "            x,y = odd\n",
    "            return x not in g[y] or any(i != x and i != y and x not in g[i] and y not in g[i] \n",
    "                                        for i in range(1,n+1))\n",
    "        if m==4:\n",
    "            a,b,c,d = odd\n",
    "            return  b not in g[a] and d not in g[c] or \\\n",
    "                    c not in g[a] and d not in g[b] or \\\n",
    "                    d not in g[a] and c not in g[b]\n",
    "        \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2] # 获取每个节点度数\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0:\n",
    "            return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(i != x and i != y and x not in g[i] and y not in g[i] for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or c not in g[a] and d not in g[b] or d not in g[a] and c not in g[b]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        edge = defaultdict(set)\n",
    "        for i,j in edges:\n",
    "            edge[i].add(j)\n",
    "            edge[j].add(i)\n",
    "        point=[item[0] for item in edge.items() if len(item[1])%2 ==1]\n",
    "        if len(point) == 0:\n",
    "            return True\n",
    "        elif len(point) == 2:\n",
    "            if point[0]not in edge[point[1]]:\n",
    "                return True\n",
    "            else:\n",
    "                for k in range(1,n):\n",
    "                    if (k!=point[0] and k!=point[1]) and (k not in edge[point[0]] and k not in edge[point[1]]):\n",
    "                        return True\n",
    "                return False\n",
    "        elif len(point)==4: \n",
    "            if (point[0] not in edge[point[1]] and point[2] not in edge[point[3]])or\\\n",
    "            (point[0]not in edge[point[2]] and point[1] not in edge[point[3]])or\\\n",
    "            (point[0]not in edge[point[3]] and point[1] not in edge[point[2]]):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "                \n",
    "        else: return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        edge = defaultdict(set)\n",
    "        point = []\n",
    "        for i,j in edges:\n",
    "            edge[i].add(j)\n",
    "            edge[j].add(i)\n",
    "        for item in edge.items():\n",
    "            if len(item[1])%2 == 1:\n",
    "                point.append(item[0])\n",
    "        if len(point) == 0:\n",
    "            return True\n",
    "        elif len(point) == 2:\n",
    "            if point[0]not in edge[point[1]]:\n",
    "                return True\n",
    "            else:\n",
    "                for k in range(1,n):\n",
    "                    if (k!=point[0] and k!=point[1]) and (k not in edge[point[0]] and k not in edge[point[1]]):\n",
    "                        return True\n",
    "                return False\n",
    "        elif len(point)==4: \n",
    "            if (point[0] not in edge[point[1]] and point[2] not in edge[point[3]])or\\\n",
    "            (point[0]not in edge[point[2]] and point[1] not in edge[point[3]])or\\\n",
    "            (point[0]not in edge[point[3]] and point[1] not in edge[point[2]]):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "                \n",
    "        else: return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        graph = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            graph[x].add(y)\n",
    "            graph[y].add(x)\n",
    "        odds = set()\n",
    "        for node in graph.keys():\n",
    "            if graph[node].__len__()%2==1:\n",
    "                odds.add(node)\n",
    "        m = len(odds)\n",
    "        odds = list(odds)\n",
    "        if m==0:\n",
    "            return True\n",
    "        if m == 2:\n",
    "            a, b = odds[0], odds[1]\n",
    "            if a not in graph[b]:\n",
    "                return True\n",
    "            for node in range(1, n+1):\n",
    "                if node == a or node==b:\n",
    "                    continue\n",
    "                if node not in graph[a] and node not in graph[b]:\n",
    "                    return True\n",
    "            return False\n",
    "        if m == 4:\n",
    "            a, b, c, d = odds\n",
    "            return (a not in graph[b] and c not in graph[d]) | \\\n",
    "                    (a not in graph[c] and b not in graph[d]) | \\\n",
    "                    (a not in graph[d] and c not in graph[b])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        # build adjacency list of undirected graph\n",
    "        g = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            g[u].add(v)\n",
    "            g[v].add(u)\n",
    "        \n",
    "        # find vertices with odds degree\n",
    "        odds = [u for u in g if len(g[u]) % 2]\n",
    "\n",
    "        # number of vertices with odds degree\n",
    "        m = len(odds)\n",
    "        if m == 0: \n",
    "            # connect nothing\n",
    "            return True\n",
    "        if m == 2:\n",
    "            u, v = odds\n",
    "            # connect 1 edge: u-v\n",
    "            if u not in g[v]:\n",
    "                return True \n",
    "            else:\n",
    "                for i in range(1, n + 1):\n",
    "                    # connect 2 edges: edge i-u and edge i-v\n",
    "                    if i not in {u, v} and u not in g[i] and v not in g[i]:\n",
    "                        return True \n",
    "\n",
    "        # connect 2 edges\n",
    "        # 1. edge a-b and edge c-d\n",
    "        # 2. edge a-c and edge b-d\n",
    "        # 3. edge a-d and edge b-c                \n",
    "        if m == 4:\n",
    "            a, b, c, d = odds\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2: \n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(i != x and i != y and x not in g[i] and y not in g[i]\n",
    "            for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd \n",
    "            return (b not in g[a] and d not in g[c]) or \\\n",
    "                   (c not in g[a] and d not in g[b]) or \\\n",
    "                   (d not in g[a] and c not in g[b]) \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        \n",
    "        if m == 0:\n",
    "            return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = [i for i, nb in g.items() if len(nb) % 2]\n",
    "        m = len(odd)\n",
    "        if m == 0: return True\n",
    "        if m == 2:\n",
    "            x, y = odd\n",
    "            return x not in g[y] or any(\n",
    "                i != x and i != y and x not in g[i] and y not in g[i]\n",
    "                for i in range(1, n + 1))\n",
    "        if m == 4:\n",
    "            a, b, c, d = odd\n",
    "            return b not in g[a] and d not in g[c] or \\\n",
    "                   c not in g[a] and d not in g[b] or \\\n",
    "                   d not in g[a] and c not in g[b]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addEdges(self, n: int, edges: List[List[int]],edge: List[int]) -> bool:\n",
    "        dic = {}\n",
    "        edges.append(edge)\n",
    "        for ii in range(n):\n",
    "            dic[ii+1] = 0\n",
    "        for edge in edges:\n",
    "            dic[edge[0]] += 1\n",
    "            dic[edge[1]] += 1\n",
    "        \n",
    "        verticeOdd = []\n",
    "        for key,value in dic.items():\n",
    "            if value%2 ==1:\n",
    "                verticeOdd.append(key)\n",
    "        if len(verticeOdd) == 0:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        dic = {}\n",
    "        for ii in range(n):\n",
    "            dic[ii+1] = 0\n",
    "        for ii,edge in enumerate(edges):\n",
    "            if edge[0]>edge[1]:\n",
    "                edges[ii] = [edge[1],edge[0]]\n",
    "            dic[edge[0]] += 1\n",
    "            dic[edge[1]] += 1\n",
    "        \n",
    "        verticeOdd = []\n",
    "        for key,value in dic.items():\n",
    "            if value%2 ==1:\n",
    "                verticeOdd.append(key)\n",
    "        m = len(verticeOdd)\n",
    "        if m == 0:\n",
    "            return True\n",
    "        if m not in [2,4]:\n",
    "            return False\n",
    "\n",
    "\n",
    "        flag = 0\n",
    "        for vi in verticeOdd:\n",
    "            for vj in verticeOdd:\n",
    "                edgeTmp = [vi,vj]\n",
    "                if vj>vi and edgeTmp not in edges:\n",
    "                    edges2 = edges[:]\n",
    "                    flag = self.addEdges(n,edges2,edgeTmp)\n",
    "                    if flag == 1:\n",
    "                        return True\n",
    "                    if m==4:\n",
    "                        edgesTmp = edges[:]\n",
    "                        edgesTmp.append(edgeTmp)\n",
    "                        edgeC = verticeOdd[:]\n",
    "                        edgeC.remove(vi)\n",
    "                        edgeC.remove(vj)\n",
    "                        if edgeC not in edges:\n",
    "                            flag = self.addEdges(n,edgesTmp,edgeC)\n",
    "                            if flag == 1:\n",
    "                                return True\n",
    "        if m==2:\n",
    "            #construct dictionary of odd\n",
    "            dicOdd = {}\n",
    "            v1 = verticeOdd[0]\n",
    "            v2 = verticeOdd[1]\n",
    "            dicOdd[v1]=set()\n",
    "            dicOdd[v2]=set()\n",
    "            for edge in edges:\n",
    "                if edge[0]==v1:\n",
    "                    dicOdd[v1].add(edge[1])\n",
    "                if edge[1]==v1:\n",
    "                    dicOdd[v1].add(edge[0])\n",
    "                if edge[0]==v2:\n",
    "                    dicOdd[v2].add(edge[1])\n",
    "                if edge[1]==v2:\n",
    "                    dicOdd[v2].add(edge[0])\n",
    "            for vi in range(1,n+1):\n",
    "                if vi not in verticeOdd and vi not in dicOdd[v1] and vi not in dicOdd[v2]:\n",
    "                    if vi<v1:\n",
    "                        edge1 = [vi,v1]\n",
    "                    else:\n",
    "                        edge1 = [v1,vi]\n",
    "                    if vi<v2:\n",
    "                        edge2 = [vi,v2]\n",
    "                    else:\n",
    "                        edge2 = [v2,vi]\n",
    "                    edges2 = edges[:]\n",
    "                    edges2.append(edge1)\n",
    "                    flag = self.addEdges(n,edges2,edge2)\n",
    "                    if flag == 1:\n",
    "                        return True\n",
    "        \n",
    "        return False\n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        d = Counter()\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "            d[a] += 1\n",
    "            d[b] += 1\n",
    "            \n",
    "        p = [i for i, x in d.items() if x % 2]\n",
    "        x = len(p)\n",
    "        if x == 0: return True\n",
    "        if x == 2:\n",
    "            a, b = p \n",
    "            if a not in g[b] and b not in g[a]: return True\n",
    "            for j in range(1, n+1):\n",
    "                if j != a and j != b and j not in g[a] and j not in g[b]:\n",
    "                    return True\n",
    "            return False\n",
    "        if x == 4:\n",
    "            a, b, c, d = p \n",
    "            return a not in g[b] and c not in g[d] or \\\n",
    "                   a not in g[c] and b not in g[d] or \\\n",
    "                   a not in g[d] and b not in g[c]\n",
    "        return False    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        deg = [set() for _ in range(n + 1)]\n",
    "\n",
    "        for i, j in edges:\n",
    "            deg[i].add(j)\n",
    "            deg[j].add(i)\n",
    "\n",
    "        nodes = []\n",
    "        for idx, i in enumerate(deg):\n",
    "            if len(i) % 2:\n",
    "                nodes.append(idx)\n",
    "        \n",
    "        print(nodes)\n",
    "        if len(nodes) == 0:\n",
    "            return True\n",
    "        if len(nodes) == 2:\n",
    "            return n != len(deg[nodes[0]] | deg[nodes[1]])\n",
    "        if len(nodes) == 4:\n",
    "            a, b, c, d = nodes\n",
    "            sols = [[(a, c), (b, d)], [(a, b), (c, d)], [(a, d), (b, c)]]\n",
    "            for x, y in sols:\n",
    "                if (not x[0] in deg[x[1]]) and (not y[0] in deg[y[1]]):\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        deg = [0] * (n + 1)\n",
    "        s = set()\n",
    "        for i, j in edges:\n",
    "            deg[i] += 1\n",
    "            deg[j] += 1\n",
    "            s.add((i, j))\n",
    "            s.add((j, i))\n",
    "        odd = []\n",
    "        for i in range(1, n + 1):\n",
    "            if deg[i] % 2 == 1:\n",
    "                odd.append(i)\n",
    "        if len(odd) == 0:\n",
    "            return True\n",
    "        if len(odd) == 2:\n",
    "            i, j = odd[0], odd[1]\n",
    "            if (i, j) not in s:\n",
    "                return True\n",
    "            for k in range(1, n + 1):\n",
    "                if k == i or k == j:\n",
    "                    continue\n",
    "                if (i, k) not in s and (k, j) not in s:\n",
    "                    return True\n",
    "        if len(odd) == 4:\n",
    "            a, b, c, d = odd[0], odd[1], odd[2], odd[3]\n",
    "            if (a, b) not in s and (c, d) not in s:\n",
    "                return True\n",
    "            if (a, c) not in s and (b, d) not in s:\n",
    "                return True\n",
    "            if (a, d) not in s and (b, c) not in s:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        deg = [0] * (n + 1)\n",
    "        g = [set() for _ in range(n + 1)]\n",
    "        for a, b in edges:\n",
    "            # if (a == 2 and b == 3) or (a == 3 and b == 2)\n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        cnt = 0\n",
    "        d = []\n",
    "        for i in range(n + 1):\n",
    "            if deg[i] & 1:\n",
    "                d.append(i)\n",
    "        # print(d)\n",
    "        if len(d) == 0:\n",
    "            return True\n",
    "        if len(d) == 2:\n",
    "            if d[0] not in g[d[1]]:\n",
    "                return True\n",
    "            for i in range(1, n + 1):\n",
    "                if i not in d and i not in g[d[0]] and i not in g[d[1]]:\n",
    "                    return True\n",
    "            return False\n",
    "        if len(d) > 4:\n",
    "            return False\n",
    "        n1, n2, n3, n4 = d\n",
    "        if n1 not in g[n2] and n3 not in g[n4]:\n",
    "            return True\n",
    "        if n1 not in g[n3] and n2 not in g[n4]:\n",
    "            return True\n",
    "        if n1 not in g[n4] and n2 not in g[n3]:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        deg = [0] * n\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            x, y = x - 1, y - 1\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        odd = set()\n",
    "        for i in range(n):\n",
    "            if deg[i] & 1:\n",
    "                odd.add(i)\n",
    "        if len(odd) & 1 or len(odd) > 4: return False\n",
    "        if not len(odd): return True\n",
    "        if len(odd) == 2:\n",
    "            a, b = odd\n",
    "            if b not in g[a]: return True\n",
    "            for i in range(n):\n",
    "                if i != a and i != b and a not in g[i] and b not in g[i]:\n",
    "                    return True\n",
    "        else:\n",
    "            for x, y in permutations(odd, 2):\n",
    "                a, b = odd - set([x, y])\n",
    "                if x not in g[y] and a not in g[b]: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        s = set()\n",
    "        d = [0] * (n + 1)\n",
    "        for x, y in edges:\n",
    "            d[x] += 1\n",
    "            d[y] += 1\n",
    "            s.add((x, y))\n",
    "            s.add((y, x))\n",
    "        \n",
    "        odd = list()\n",
    "        even = list()\n",
    "        for i in range(1, n + 1):\n",
    "            if d[i] & 1:\n",
    "                odd.append(i)\n",
    "            else:\n",
    "                even.append(i)\n",
    "        \n",
    "        if len(odd) == 0:\n",
    "            return True\n",
    "        if len(odd) == 2:\n",
    "            x, y = odd\n",
    "            if (x, y) not in s:\n",
    "                return True\n",
    "            for cand in even:\n",
    "                if (x, cand) not in s and (y, cand) not in s:\n",
    "                    return True\n",
    "            return False\n",
    "        if len(odd) == 4:\n",
    "            a, b, c, d = odd\n",
    "            if (a, b) not in s and (c, d) not in s:\n",
    "                return True\n",
    "            if (a, c) not in s and (b, d) not in s:\n",
    "                return True\n",
    "            if (a, d) not in s and (b, c) not in s:\n",
    "                return True\n",
    "            return False\n",
    "        return False\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        deg = [0] * (n + 1)\n",
    "        g = [set() for _ in range(n + 1)] \n",
    "        for u,v in edges:\n",
    "            deg[u] += 1\n",
    "            deg[v] += 1\n",
    "            g[u].add(v)\n",
    "            g[v].add(u)\n",
    "        z = []\n",
    "        p = []\n",
    "        for i,d in enumerate(deg):\n",
    "            if d & 1:\n",
    "                z.append(i)\n",
    "            else:\n",
    "                p.append(i)\n",
    "        p = p[1:]\n",
    "        m = len(z)\n",
    "        if m & 1:\n",
    "            return False\n",
    "        if m > 4:\n",
    "            return False\n",
    "        if m == 0:\n",
    "            return True\n",
    "        k = []\n",
    "        for u in z:\n",
    "            for v in z:\n",
    "                if u == v:\n",
    "                    continue\n",
    "                if v not in g[u]:\n",
    "                    k.append((u,v))\n",
    "        if m == 2:\n",
    "            if len(k):\n",
    "                return True\n",
    "            else:\n",
    "                for u in p:\n",
    "                    for v in z:\n",
    "                        if v in g[u]:\n",
    "                            break\n",
    "                    else:\n",
    "                        return True\n",
    "                return False\n",
    "        for a in k:\n",
    "            for b in k:\n",
    "                if a == b:\n",
    "                    continue\n",
    "                if a[0] != b[0] and a[0] != b[1] and a[1] != b[0] and a[1] != b[1]:\n",
    "                    return True\n",
    "        return False\n",
    "s = Solution()\n",
    "s.isPossible(4,[[1,2],[2,3],[2,4],[3,4]])\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        g = [set() for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a-1].add(b-1)\n",
    "            g[b-1].add(a-1)\n",
    "        count = []\n",
    "        for i in range(n):\n",
    "            if len(g[i]) == n-1 and not n % 2:\n",
    "                return False\n",
    "            if len(g[i]) % 2:\n",
    "                count.append(i)\n",
    "        lc = len(count)\n",
    "        if lc > 4:\n",
    "            return False\n",
    "        if lc == 0:\n",
    "            return True\n",
    "        if lc == 2:\n",
    "            a, b = count\n",
    "            for i in range(n):\n",
    "                if a not in g[i] and b not in g[i]:\n",
    "                    return True\n",
    "            return False\n",
    "        a, b, c, d = count\n",
    "        if a not in g[b] and c not in g[d]:\n",
    "            return True\n",
    "        if a not in g[c] and b not in g[d]:\n",
    "            return True\n",
    "        if a not in g[d] and b not in g[c]:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        node = [set() for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            node[x-1].add(y-1)\n",
    "            node[y-1].add(x-1)\n",
    "        \n",
    "        nodeSet = []\n",
    "        for i in range(n):\n",
    "            if len(node[i]) % 2 == 1:   nodeSet.append(i)\n",
    "        \n",
    "        if len(nodeSet) == 0:   return True\n",
    "        if len(nodeSet) == 2:\n",
    "            if nodeSet[0] not in node[nodeSet[1]]:  return True\n",
    "            for x in range(n):\n",
    "                if x not in nodeSet and x not in node[nodeSet[0]] and x not in node[nodeSet[1]]:    return True\n",
    "        if len(nodeSet) == 4:\n",
    "            nodePair = [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 1, 2]]\n",
    "            for A, B, C, D in nodePair:\n",
    "                if nodeSet[A] not in node[nodeSet[B]] and nodeSet[C] not in node[nodeSet[D]]:   return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        node = [set() for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            node[x-1].add(y-1)\n",
    "            node[y-1].add(x-1)\n",
    "        \n",
    "        nodeSet = []\n",
    "        for i in range(n):\n",
    "            if len(node[i]) % 2 == 1:   nodeSet.append(i)\n",
    "        \n",
    "        if len(nodeSet) == 0:   return True\n",
    "        if len(nodeSet) == 2:\n",
    "            if nodeSet[0] not in node[nodeSet[1]]:  return True\n",
    "            for x in range(n):\n",
    "                if x not in nodeSet and x not in node[nodeSet[0]] and x not in node[nodeSet[1]]:    return True\n",
    "        if len(nodeSet) == 4:\n",
    "            nodePair = [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 1, 2]]\n",
    "            for A, B, C, D in nodePair:\n",
    "                if nodeSet[A] not in node[nodeSet[B]] and nodeSet[C] not in node[nodeSet[D]]:   return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        node = [set() for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            node[x-1].add(y-1)\n",
    "            node[y-1].add(x-1)\n",
    "        \n",
    "        nodeSet = []\n",
    "        for i in range(n):\n",
    "            if len(node[i]) % 2 == 1:   nodeSet.append(i)\n",
    "        \n",
    "        if len(nodeSet) == 0:   return True\n",
    "        if len(nodeSet) == 2:\n",
    "            if nodeSet[0] not in node[nodeSet[1]]:  return True\n",
    "            for x in range(n):\n",
    "                if x not in nodeSet and x not in node[nodeSet[0]] and x not in node[nodeSet[1]]:    return True\n",
    "        if len(nodeSet) == 4:\n",
    "            nodePair = [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 1, 2]]\n",
    "            for A, B, C, D in nodePair:\n",
    "                if nodeSet[A] not in node[nodeSet[B]] and nodeSet[C] not in node[nodeSet[D]]:   return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        node = [set() for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            node[x-1].add(y-1)\n",
    "            node[y-1].add(x-1)\n",
    "        \n",
    "        nodeSet = []\n",
    "        for i in range(n):\n",
    "            if len(node[i]) % 2 == 1:   nodeSet.append(i)\n",
    "        \n",
    "        if len(nodeSet) == 0:   return True\n",
    "        if len(nodeSet) == 2:\n",
    "            if nodeSet[0] not in node[nodeSet[1]]:  return True\n",
    "            for x in range(n):\n",
    "                if x not in nodeSet and x not in node[nodeSet[0]] and x not in node[nodeSet[1]]:    return True\n",
    "        if len(nodeSet) == 4:\n",
    "            nodePair = [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 1, 2]]\n",
    "            for A, B, C, D in nodePair:\n",
    "                if nodeSet[A] not in node[nodeSet[B]] and nodeSet[C] not in node[nodeSet[D]]:   return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, n: int, edges: List[List[int]]) -> bool:\n",
    "        book = [set() for i in range(n)]\n",
    "        degrees = [0 for i in range(n)]\n",
    "        for a,b in edges:\n",
    "            book[a-1].add(b-1)\n",
    "            book[b-1].add(a-1)\n",
    "            degrees[a-1]+=1\n",
    "            degrees[b-1]+=1\n",
    "        oddDegreeNodes = set()\n",
    "        for i in range(n):\n",
    "            if (degrees[i]&1)==1:\n",
    "                oddDegreeNodes.add(i)\n",
    "        if len(oddDegreeNodes)==0:\n",
    "            return True\n",
    "        if (len(oddDegreeNodes)&1)==1 or len(oddDegreeNodes)>4:\n",
    "            return False\n",
    "        if len(oddDegreeNodes)==2:\n",
    "            a,b = oddDegreeNodes\n",
    "            return a not in book[b] or any(\n",
    "                i != a and i != b and a not in book[i] and b not in book[i] for i in range(n)\n",
    "            )\n",
    "        a,b,c,d = oddDegreeNodes\n",
    "        if b not in book[a] and c not in book[d]:\n",
    "            return True\n",
    "        if c not in book[a] and b not in book[d]:\n",
    "            return True\n",
    "        if d not in book[a] and b not in book[c]:\n",
    "            return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
